#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-14 10:12 上午
# @Author  : yangdy
# @File    : 2020-07-14.120. 三角形最小路径和
# @Software: PyCharmCE
from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        ans = -1
        if not triangle:
            return ans
        n = len(triangle)
        li = 0
        for i in range(1, n):
            li = len(triangle[i])
            for j in range(li):
                if j == 0:
                    k = triangle[i-1][j]
                elif j == li - 1:
                    k = triangle[i-1][j-1]
                else:
                    k = min(triangle[i-1][j-1], triangle[i-1][j])
                triangle[i][j] += k
        ans = triangle[n-1][0]
        for i in range(1, li):
            ans = min(ans, triangle[n-1][i])
        return ans


solve = Solution()

questions = [
    ([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]],),
    ([[8], [6, 3], [9, -9, 6], [8, 7, -3, 9], [-2, 7, -2, 8, 0], [7, 6, 2, 7, 4, 0], [6, 3, -1, 4, 3, 8, 3], [-5, -3, 9, 9, -7, 3, 8, -6], [-1, 4, -9, 5, 3, -4, 2, -8, -6], [9, 5, 9, -2, 2, 1, 7, -5, -9, -6], [5, 4, -8, -2, 8, -5, -3, 4, -3, 9, 3]],),
    ([[-1], [3, 2], [-3, 1, -1]], ),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.minimumTotal(q[0]))

